class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
    {
        int next[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> ret(m, vector<int>(n, -1));

        queue<tuple<int, int, int>> q;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (mat[i][j] == 0)
                {
                    ret[i][j] = 0;
                    q.push({ i,j,0 });
                }
            }
        }

        while (!q.empty())
        {
            auto [x, y, step] = q.front();
            q.pop();

            for (auto e : next)
            {
                int nextx = x + e[0], nexty = y + e[1];
                if (nextx >= 0 && nexty >= 0 && nextx < m && nexty < n && ret[nextx][nexty] == -1)
                {
                    ret[nextx][nexty] = step + 1;
                    q.push({ nextx,nexty,step + 1 });
                }
            }
        }

        return ret;
    }
};